/**
 * @param {string} digits
 * @return {string[]}
 */
/* 
为了生成电话号码数字对应的所有字母组合，可以使用回溯法。
回溯法通过递归遍历每个数字对应的所有可能字母，逐步构建组合字符串，直到处理完所有数字。

方法思路
映射关系：建立数字到字母的映射表（如 2 对应 "abc"，3 对应 "def" 等）。
递归回溯：从第一个数字开始，递归遍历其对应的每个字母，并将当前字母加入路径。继续处理下一个数字，直到所有数字处理完毕，将路径加入结果集。
边界条件：当输入为空字符串时，直接返回空数组。
*/
var letterCombinations = function (digits) {
  if (digits.length === 0) return [];

  // 数字到字母的映射表
  const map = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
  };

  const result = [];

  // 回溯函数：处理当前数字索引，构建路径
  const backtrack = (index, path) => {
    // 当路径长度等于输入长度时，加入结果集
    if (path.length === digits.length) {
      result.push(path);
      return;
    }

    // 获取当前数字对应的字母
    const letters = map[digits[index]];

    // 遍历每个字母，递归处理下一个数字
    for (const letter of letters) {
      backtrack(index + 1, path + letter);
    }
  };

  // 从索引0开始回溯
  backtrack(0, '');

  return result;
};